package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了79.41%的用户
内存消耗：5 MB, 在所有 Go 提交中击败了44.12%的用户
 */
var n int
var f []map[int]int
var price []int
var special [][]int

func shoppingOffers(_price []int, _special [][]int, needs []int) int {

	price, special = _price, _special
	n  = len(price)
	f = make([]map[int]int, len(special) + 1)
	for i := 0; i <= len(special); i++ { f[i] = make(map[int]int, 0) }

	state := 0
	for i := len(needs) - 1; i >= 0; i-- {
		state = state * 16 + needs[i]
	}

	return dp(len(special), state)
}

func dp(x int, y int) int {

	if _, ok := f[x][y]; ok { return f[x][y] }

	if x == 0 {
		f[x][y] = 0
		for i := 0; i < n; i++ {
			c := (y >> (i * 4)) & 15
			f[x][y] += c * price[i]
		}
		return f[x][y]
	}

	f[x][y] = dp(x - 1, y)
	state := 0
	s := special[x - 1]
	for i := n - 1; i >= 0; i-- {
		c := (y >> (i * 4)) & 15
		if c < s[i] {
			state = -1
			break
		}
		state = state * 16 + (c - s[i])
	}
	if state != -1 {
		f[x][y] = min(f[x][y], dp(x, state) + s[len(s) - 1])
	}
	return f[x][y]
}

// 求最小值
func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	price := []int{2, 5}
	special := [][]int{
		{3, 0, 5},
		{1, 2, 10},
	}
	needs := []int{3, 2}
	fmt.Println(shoppingOffers(price, special, needs))  // 14
}
